/**
 * @author DCSGO
 * @version 1.0
 */
/*
来自美团8.20笔试 使两个序列完全相同求最小修改值
小团生日收到妈妈送的两个一模一样的数列作为礼物!他很开心的把玩，不过不小心没拿稳将数列摔坏了!
现在他手上的两个数列分别为A和B，长度分别为n和m。
小团很想再次让这两个数列变得一样。他现在能做两种操作:
操作一是将一个选定数列中的某一个数a改成数b，这会花费|b-a|的时间,
操作二是选择一个数列中某个数a，将它从数列中丢掉，花费|a|的时间。
小团想知道，他最少能以多少时间将这两个数列变得再次相同!
输入描述∶
第一行两个空格隔开的正整数n和m，分别表示数列A和B的长度。接下来一行n个整数，分别为A1 A2 ... An
接下来一行m个整数，分别为B1 B2 ... Bm
对于所有数据，1 <= n,m <= 2000, |Ai|,|Bi| <= 10000
输出一行一个整数，表示最少花费时间，来使得两个数列相同。
 */

@SuppressWarnings({"all"})
public class P4 {
    public static void main(String[] args) {
        int[] A = {10, 20, 30, 40};
        int[] B = {40, 30, 20, 10};
        int[][] dp = new int[B.length + 1][A.length + 1];

        System.out.println(change(A, B, 0, 0));
        System.out.println(dpChange(A, B, A.length, B.length, dp));

    }

    //改dp 分析好依赖关系 后 对着递归直接抄！
    public static int dpChange(int[] A, int[] B, int n, int m, int[][] dp) {
        //最后一行
        for (int i = n - 1; i >= 0; i--) {
            dp[m][i] = Math.abs(A[i]) + dp[m][i + 1];
        }
        //最后一列
        for (int i = m - 1; i >= 0; i--) {
            dp[i][n] = Math.abs(B[i]) + dp[i + 1][n];
        }
        for (int i = m - 1; i >= 0; i--) {//行
            for (int j = n - 1; j >= 0; j--) {//列
                int p1 = Math.abs(A[j]) + dp[i][j + 1];
                int p2 = Math.abs(B[i] + dp[i + 1][j]);
                int p3 = Math.abs(B[i] - A[j]) + dp[i + 1][j + 1];
                dp[i][j] = Math.min(p1, Math.min(p2, p3));
            }
        }
        return dp[0][0];
    }

    //从 ai 下标开始改变 A bi 下标开始改变 B 返回使 A B 完全相同的改变方法的最小改变值
    public static int change(int[] A, int[] B, int ai, int bi) {
        //终止条件
        //两序列都改到头了 改好了
        if (ai == A.length && bi == B.length) {
            return 0;
        }
        //A 没走到头但 B 已经到头了
        if (ai != A.length && bi == B.length) {
            //扔掉 ai B 不变 + 后续的 改变的最小值
            return Math.abs(A[ai]) + change(A, B, ai + 1, bi);
        }
        //B 没走到头但 A 已经到头了
        if (ai == A.length && bi != B.length) {
            //扔掉 bi A 不变 + 后续的 改变的最小值
            return Math.abs(B[bi]) + change(A, B, ai, bi + 1);
        }

        //一般情况
        //1.删掉ai
        int p1 = Math.abs(A[ai]) + change(A, B, ai + 1, bi);

        //2.删掉bi
        int p2 = Math.abs(B[bi]) + change(A, B, ai, bi + 1);

        //3.都删掉 不可能优于 p4
        //int p3 = Math.abs(A[ai]) + Math.abs(B[bi]) + change(A, B, ai + 1, bi + 1);

        //4.改 ai 或改 bi( abs(B[bi] - A[ai]) == abs(A[ai] - B[bi]) )
        int p4 = Math.abs(B[bi] - A[ai]) + change(A, B, ai + 1, bi + 1);

        //5.A[ai] == B[bi] 此时 Math.abs(B[bi] - A[ai]) == 0 同 p4
        return Math.min(p1, Math.min(p2, p4));
    }

}
